package com.algorithm.ThreeMachine2;

import java.util.*;

public class ThreeMachine2 {
    public static void main(String[] args) {
        List<List<Work>> jobs=new ArrayList<>();
        System.out.println("在机器数为3的情况下，输入工作数：");
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        generateData(n,jobs);
        //初始化作业列表

//        {
//            List<Work> job=new ArrayList<>();
//            Work work=new Work(0,3);
//            job.add(work);
//            work=new Work(1,2);
//            job.add(work);
//            work=new Work(2,2);
//            job.add(work);
//            jobs.add(job);
//
//            job=new ArrayList<>();
//            work=new Work(0,2);
//            job.add(work);
//            work=new Work(2,1);
//            job.add(work);
//            work=new Work(1,4);
//            job.add(work);
//            jobs.add(job);
//
//            job=new ArrayList<>();
//            work=new Work(1,4);
//            job.add(work);
//            work=new Work(2,3);
//            job.add(work);
//            jobs.add(job);
//        }


        //输出作业列表
        for(int i=0;i<jobs.size();i++){
            for(int j=0;j<jobs.get(i).size();j++){
                System.out.println(jobs.get(i).get(j).machine+" "+jobs.get(i).get(j).time);
            }
            System.out.println();
        }

        //定义优先队列的比较器
        Comparator<Node> cmp=new Comparator<Node>() {
            @Override
            public int compare(Node node, Node t1) {
                return node.prospect-t1.prospect;   //从小到大进行排列
            }
        };

        //创建优先队列
        PriorityQueue<Node> queue=new PriorityQueue<>(cmp);
//        Queue<Node> queue=new LinkedList<>();

        //创建根节点
        Node rootNode=new Node();
        //初始化根节点
        rootNode.jobIndex=0;  //根节点对应0号任务
        rootNode.workIndex=-1;  //0号任务没有开始
        for(int i=0;i<jobs.size();i++){
            rootNode.workIndexs[i]=-1;
        }
        rootNode.costTime=0;  //当前耗费时间为0
        for(int i=0;i<jobs.size();i++){
            rootNode.jobTime[i]=0;
        }
        for(int i=0;i<3;i++){
            rootNode.machineTime[i]=0;
        }
        rootNode.count=0;  //这是执行的第0个任务
        rootNode.father=null;  //根节点没有父节点
        int tempTime=0;
        int[] jobTime=new int[jobs.size()];
        for(int i=0;i<jobs.size();i++){
            for(int j=0;j<jobs.get(i).size();j++){
                jobTime[i]+=jobs.get(i).get(j).time;
            }
        }
        for(int i=0;i<jobs.size();i++){
            if(jobTime[i]>tempTime){
                tempTime=jobTime[i];
            }
        }
        int[] machineTime={0,0,0};
        for(int i=0;i<jobs.size();i++){
            for(int j=0;j<jobs.get(i).size();j++){
                machineTime[jobs.get(i).get(j).machine]+=jobs.get(i).get(j).time;
            }
        }
        for(int i=0;i<3;i++){
            if(machineTime[i]>tempTime){
                tempTime=machineTime[i];
            }
        }
        rootNode.prospect=tempTime;  //根节点的前途是耗费时间最长的那个工作所耗费的时间

        //将根节点放入队列中
        queue.offer(rootNode);

        //定义全场最佳值
        int bestTime=100000000;
        Node resultNode=null;

        //程序开始时间，毫秒级
        long startTime=System.currentTimeMillis();
        //对队列进行循环
        while (!queue.isEmpty()){
            //取出队首元素
            Node fatherNode=queue.poll();

            //如果队首节点没有前途，则不进行扩展
            if(fatherNode.prospect>=bestTime){
                continue;
            }
            //如果队首节点是最后一个工作对应的节点，更新全场最佳值，不进行扩展
            if(fatherNode.count==3*n){
                if(fatherNode.costTime<bestTime){
                    bestTime=fatherNode.costTime;
                    resultNode=fatherNode;
                }
                System.out.println();
                System.out.println(fatherNode.costTime);
                while(fatherNode!=rootNode){
                    System.out.print(fatherNode.jobIndex+","+fatherNode.workIndex+"<- ");
                    fatherNode=fatherNode.father;
                }

                continue;
            }
            for(int k=0;k<jobs.size();k++){
                //对队首节点进行扩展
                //1.1创建新节点
                Node newNode=new Node();
                //1.2给新节点赋值
                newNode.jobIndex=k;
                newNode.workIndex=fatherNode.workIndexs[k]+1;
                if(newNode.workIndex<jobs.get(newNode.jobIndex).size()){
                    newNode.count=fatherNode.count+1;
                    newNode.father=fatherNode;
                    for(int i=0;i<jobs.size();i++){
                        newNode.workIndexs[i]=fatherNode.workIndexs[i];
                    }
                    newNode.workIndexs[newNode.jobIndex]=newNode.workIndex;
                    for(int i=0;i<jobs.size();i++){
                        newNode.jobTime[i]=fatherNode.jobTime[i];
                    }
                    for(int i=0;i<3;i++){
                        newNode.machineTime[i]=fatherNode.machineTime[i];
                    }
                    //newNode.jobTime[i]=max{fatherNode.jobTime[i],fatherNode.machineTime[jobs[i][j].machine]}+jobs[i][j].time  j=newNode.workIndex
                    //newNode.machineTime[jobs[i][j].machine]=newNode.jobTime[i]
                    if(fatherNode.jobTime[newNode.jobIndex]>fatherNode.machineTime[jobs.get(newNode.jobIndex).get(newNode.workIndex).machine]){
                        newNode.jobTime[newNode.jobIndex]=fatherNode.jobTime[newNode.jobIndex]+jobs.get(newNode.jobIndex).get(newNode.workIndex).time;
                        newNode.machineTime[jobs.get(newNode.jobIndex).get(newNode.workIndex).machine]=newNode.jobTime[newNode.jobIndex];
                    }else {
                        newNode.jobTime[newNode.jobIndex]=fatherNode.machineTime[jobs.get(newNode.jobIndex).get(newNode.workIndex).machine]+jobs.get(newNode.jobIndex).get(newNode.workIndex).time;
                        newNode.machineTime[jobs.get(newNode.jobIndex).get(newNode.workIndex).machine]=newNode.jobTime[newNode.jobIndex];
                    }
                    //newNode.costTime=max{newNode.jobTime[newNode.jobIndex],fatherNode.costTime}
                    if(newNode.jobTime[newNode.jobIndex]>fatherNode.costTime){
                        newNode.costTime=newNode.jobTime[newNode.jobIndex];
                    }else {
                        newNode.costTime=fatherNode.costTime;
                    }
                    for(int i=0;i<3;i++){
                        machineTime[i]=newNode.machineTime[i];
                    }
                    for(int i=0;i<jobs.size();i++){
                        jobTime[i]=newNode.jobTime[i];
                    }
                    for(int i=0;i<jobs.size();i++){
                        for(int j=newNode.workIndexs[i]+1;j<jobs.get(i).size();j++){
                            jobTime[i]+=jobs.get(i).get(j).time;
                            machineTime[jobs.get(i).get(j).machine]+=jobs.get(i).get(j).time;
                        }
                    }
                    tempTime=0;
                    for(int i=0;i<jobs.size();i++){
                        if(jobTime[i]>tempTime){
                            tempTime=jobTime[i];
                        }
                    }
                    for(int i=0;i<3;i++){
                        if(machineTime[i]>tempTime){
                            tempTime=machineTime[i];
                        }
                    }
                    newNode.prospect=tempTime;
//                    if(newNode.costTime>fatherNode.prospect){
//                        newNode.prospect=newNode.costTime;
//                    }else {
//                        newNode.prospect=fatherNode.prospect;
//                    }
                    //1.3将新节点放入队列中。
                    queue.offer(newNode);
                }
            }
        }
        long endTime=System.currentTimeMillis();
        System.out.println();
        System.out.println(endTime-startTime);
    }

    public static List<List<Work>> generateData(int n,List<List<Work>> jobs) {    //产生数据 工作数及时序不定随机产生  机器数定为10
        while(n>0) {
            List<Work> job=new ArrayList<>();
            List list = new ArrayList<>();
            Random r = new Random();
            for(int i=0; i<3;){
                int order = r.nextInt(3);
                int time = r.nextInt(10)+1;
                if(!list.contains(order)) {
                    i++;
                    list.add(order);
                    Work work=new Work(order,time);
                    job.add(work);
                }
            }
            jobs.add(job);
            n=n-1;
        }
        return jobs;
    }


    /**
     获取精确到毫秒的时间戳
     * @param date
     * @return
     **/
//    public static Long getTimestamp(Date date){
//        if (null == date) {
//            return (long) 0;
//        }
//        String timestamp = String.valueOf(date.getTime());
//        return Long.valueOf(timestamp);
//    }

//    public static void main(String[] args) {
//        Date d = new Date();
//        System.out.println(getTimestamp(d));
//    }
}
